package bfs;

import java.util.*;

/**
 * 滑动谜题
 */
public class SlidingPuzzle {

    public int silidingPuzzle(int[][] board) {
        int m = 2, n = 3;
        StringBuilder sb = new StringBuilder();
        String target = "123450";
        // 将 2x3的数组转换为字符串作为BFS的起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++ ) {
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();

        // 记录一维字符串的相邻索引
        int[][] neighbor = new int[][] {
                {1, 3},
                {0, 4, 2},
                {1, 5},
                {0, 4},
                {3, 1, 5},
                {4, 2}
        };

        // ********** BFS 算法框架开始 ***********
        Queue<String> q = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        // 从起点开始BFS搜索
        q.offer(start);
        visited.add(start);

        int step = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                // 判断是否到达目标局面
                if (target.equals(cur)) {
                    return step;
                }
                // 找到数字0的索引
                int index = 0;
                for (; cur.charAt(index) !=0; index++) {
                    // 将数字0和相邻的数字交换位置
                    for (int adj : neighbor[index]) {
                        String new_board = swap(cur.toCharArray(), adj ,index);
                        // 防止走回头路
                        if (!visited.contains(new_board)) {
                            q.offer(new_board);
                            visited.add(new_board);
                        }
                    }
                }
                step++;
            }
        }
        // ********** BFS 算法框架结束 ***********
        return -1;
    }

    private String swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }
}
